1. Field Of The Invention
This invention relates to conventional convolutional coding methods and apparatus and, more particularly, to a method and apparatus for encoding and decoding a finite length digital data bit stream to a Periodic Convolutional Code Block (PCCB) format, which eliminates the overhead bits required for conventional convolutional encoding and decoding of a digital data bit stream of finite length.
2. Description of The Prior Art
Historically, conventional convolutional codes were first disclosed in the publication by Elias, P., "Coding for Noisy Channels," I.R.E. Conv. Record, 1955, Pt. 4, pages 37-46. Excellent treatment of convolutional code theory and apparatus for implementing the code can be found in several publications, including Berlekamp, E. R., Algebriac Coding Theory, McGraw-Hill Book Co., New York, 1968, pages 388-394, and Peterson, W. W., and Weldon, Jr., E. J., Error-Correcting Codes, 2d Ed., The MIT Press, Cambridge, Mass., 1972, pages 392-448.
It is well known in the coding art that conventional convolutional coding and decoding works best when the digital data bit stream is of infinite duration or length. However, when the digital data bit stream is of finite length, both encoding and decoding of a conventional convolutional code requires overhead bits to trick the respective conversion process into thinking the digital data bit stream is of an infinite length. This results in a waste of transmission capacity.
A very brief description of convolutional encoding may be helpful. In FIG. 1, the components within block 40 make up a conventional convolutional encoder of the type described at pages 390 and 305, respectively, of the above-mentioned publications.
The digital data bit stream of finite length to be encoded in PCCB format, designated generally by the reference letter X, is applied via a line 10 to a first input 12 of a selection device 14. The output signal at output 16 of selection device 14 is applied via a line 18 to an input stage 20 of a shift register 22. The last stage of shift register 22 is connected to a line 24 which provides the encoded information symbols, designated generally by the reference letter X.sub.n, of the output PCCB code pairs.
A plurality of individual taps are provided for specific stages of shift register 22 in conformance with the generator polynomial of the particular conventional convolutional code being employed to generate the parity symbols, as is well known in the art. Specifically, for illustrative purposes only, an individual tap is provided for stages 1, 3, 6 and 7 of shift register 22, although tap placement is determined by orthogonality requirements in each particular case. These taps, in turn, are connected to inputs of a modulo-2 adder 26. The output of modulo-2 adder 26 is applied to a line 28. The output signals on line 28 are the parity symbols, designated generally by the reference letter U.sub.n, of the output pairs of the PCCB.
In the illustrative PCCB encoder apparatus shown in FIG. 1, the conventional convolutional code being employed has a constraint length K=7 and a code rate .rho.=1/2, since for each information symbol X.sub.n there is a corresponding parity symbol U.sub.n. (Code rate .rho. is defined as the ratio of the number of information symbols K to the corresponding number of convolutional code symbols N in a constraint length). This convolutional code is a simple one.
Each time the data in register 22 is shifted, a new parity symbol and information symbol are outputted. Thus, K different parity symbols are generated corresponding to the K different positions of each bit within the register. These parity symbols are used to decode that information bit. Since the generation of parity symbols does not begin until register 22 is full, the first K bits only contribute to a few of the parity symbols, i.e., the first bit contributes to the first parity symbol, the second bit to the first two parity symbols, etc.
Similarly, at the end of the incoming bit stream, a parity symbol is generated with the B.sup.th bit, where B is the length of the finite bit stream, in the input stage of the shift register but no more information is available to generate parity symbols with the last K information bits at each of the K shift register positions. The result is that dummy bits must be supplied at the beginning and/or end of the bit stream to generate the required number of parity symbols for each information symbol. The required overhead bits must be equal to or greater than the smaller of two numbers K and R, the constraint length of the conventional convolutional code measured in information symbols K or parity symbols R=N-K. These overhead bits S must be considered surplusage in the sense that they carry no information content in themselves. When a low-performance conventional convolutional code having small values of either K or R is being used, the required S overhead bits are not that detrimental to the overall system performance. When, however, a high-performance conventional convolutional code having a very long constraint length (K and R=N-K are both large) is being used, the required S overhead bits become very detrimental to system performance. This becomes especially noticeable when short bursts of digital data information bits are being sent using a very high-performance conventional convolutional code. Such is the case in satellite communications, for example, where time division multiple access (TDMA) transmissions of short burst length are using very high-performance conventional convolutional codes to achieve high information rate communications with low probabilities of bit error after FEC decoding. In such satellite communication systems, the required overhead bits S for each TDMA burst are very detrimental to system performance. For example, when a very high-performance rate 7/8 conventional convolutional code having a constraint length of K=336 information bits and R=48 parity symbols is being used, the minimum number of overhead bits S required for a TDMA burst of 336 or more information data bits is equal to R=48. In other TDMA conventional convolutionally encoded burst schemes, from 20-100 overhead bits S are required for each burst. It is, therefore, apparent that these required overhead bits S are very detrimental to the TDMA system performance.